package com.heng.test;



import java.lang.String;
import java.util.*;

public class Main {
    public static void main(String[] args) {
//        TypeReference typeReference = new TypeReference<String>() {
//        };
        int[][] w;
        new StringBuffer().append("ssa");
        ArrayList[] adj = new ArrayList[10];

        System.out.println(Integer.toBinaryString(-10));
        System.out.println(Integer.toBinaryString(~9));
        Set<Integer> set = new HashSet<>();
        set.add(1);
        Integer i = set.stream().max((o1, o2) -> o1 - o2).get();
        System.out.println(i);

        System.out.println(3/2);
        System.out.println();

        String s = "#b#a#b";
        char[] c = new char[10];

        new String(c,0,2);

        String strs = "aabaabaaaa";

        int n = strs.length();
        int[] ne = new int[n + 1];
        ne[1] = 0;

        for (int j = 2, k = 0; j <= n; j++) {
            while (k != 0 && strs.charAt(j - 1) != strs.charAt(k)) k = ne[k];
            if (strs.charAt(j - 1) == strs.charAt(k)) k++;
            ne[j] = k;
        }
        System.out.println(Arrays.toString(ne));

        String sp = "caabaabaabaabaaaab";
        int m = sp.length();

        for (int i2 = 0, j = 0; i2 < m; i2++) {
            while (j != 0 && strs.charAt(j) != sp.charAt(i2)) j = ne[j];
            if (j < n - 1 && strs.charAt(j) == sp.charAt((i2))) j++;
            if (j == n - 1) System.out.println(i2 - n + 2);

            System.out.println("i="+i2+" j="+j);
        }

        // 取x的低位2次幂
        System.out.println(Integer.toBinaryString(19));
        System.out.println(Integer.toBinaryString(20));
        System.out.println(Integer.toBinaryString(21));
        System.out.println(Integer.toBinaryString(22));
        /*
        * 负数x的二进制位
        * x = ~-(x + 1)
        * -20
        * 19
        * */

        int[] arr = {1,2,3,4,5,6,7,8};
        int[] tree = new int[9];

        for (int x = 0; x < 8; x++) {
            int delta = arr[x];
            for (int y = x + 1; y < 9; y+=y & -y) {
                tree[y] += delta;
            }
        }
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(tree));

        Node[] tr = new Node[4 * 10];
        build(1,1,10,tr);

        for (int x = 0; x < 4 * 10; x++) {
            if (tr[x]!=null)
                System.out.println("x: " + x + " " + tr[x].sum);
        }
        System.out.println();
        int query = query(1, 1, 10, tr);
        System.out.println(query);
        System.out.println();

        update(1,1,10,1,tr);
        for (int x = 0; x < 4 * 10; x++) {
            if (tr[x]!=null)
                System.out.println("x: " + x + " " + tr[x].sum);
        }
        int query1 = query(1, 1, 10, tr);
        System.out.println(query1);


    }

    static void build(int p, int l, int r, Node[] tr) {
        //
        int[] w = {0,5,2,0,1,9,7,2,1,2,3};

        tr[p] = new Node(l, r, w[l]);
        if (l == r) return;
        int m = l + r >> 1;
        build(p << 1,l ,m, tr);
        build(p << 1 | 1,m + 1 ,r, tr);
        tr[p].sum = tr[p << 1].sum + tr[p << 1|1].sum;
    }

    static void update(int p, int x, int k, Node[] tr) {
        if (tr[p].l == x && tr[p].r == x) {
            tr[p].sum += k;
            return;
        }
        int m = tr[p].l + tr[p].r>>1;
        if (x <= m) update(p<<1,x,k,tr);
        if (x > m) update(p<<1 | 1, x, k, tr);
        tr[p].sum = tr[p << 1].sum + tr[p << 1 | 1].sum;
    }

    static void update(int p, int x, int y, int k , Node[] tr) {
        if (x <= tr[p].l && tr[p].r <= y) {
            tr[p].sum +=(tr[p].r - tr[p].l + 1)*k;
            tr[p].add+=k;
            return;
        }
        int m = tr[p].l + tr[p].r>>1;
        pushdown(p,tr);
        if (x<=m) update(p<<1,x,y,k,tr);
        if (y>m) update(p<<1|1,x,y,k,tr);
        tr[p].sum = tr[p<<1].sum+tr[p<<1|1].sum;
    }

    private static void pushdown(int p, Node[] tr) {
        if(tr[p].add!=0) {
            tr[p<<1].sum+=tr[p].add*(tr[p<<1].r-tr[p<<1].l+1);
            tr[p<<1|1].sum+=tr[p].add*(tr[p<<1|1].r-tr[p<<1|1].l+1);
            tr[p<<1].add+=tr[p].add;
            tr[p<<1|1].add+=tr[p].add;
            tr[p].add=0;

        }
    }

    static int query (int p, int x, int y, Node[] tr) {
        if (x <= tr[p].l && tr[p].r <= y) {
            return tr[p].sum;
        }
        int m = tr[p].l + tr[p].r>>1;
        int sum=0;
        if(x<=m)sum+=query(p<<1,x,y,tr);
        if(y>m)sum+=query(p<<1|1,x,y,tr);
        return sum;
    }

    static class Node {
        int l,r,sum,add;
        public Node (int l, int r, int sum) {
            this.l = l;
            this.r = r;
            this.sum = sum;
        }
        public Node (int l, int r, int sum,int add) {
            this.l = l;
            this.r = r;
            this.sum = sum;
            this.add = add;
        }
    }
}